package com.leetcode;

/**
 * 208. 实现 Trie (前缀树)
 * 使用数组来固定维护26分叉, 空间浪费严重, 而且分叉树固定无法改动, 但是速度更快一点
 *
 * @author fy
 * @date 2022/4/19 9:37
 */
public class Solution208_1 {

    class Trie {

        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            this.children = new Trie[26];
            this.isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            if (!node.isEnd) {
                node.isEnd = true;
            }
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                int index = prefix.charAt(i) - 'a';
                if (node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }

    }

}
